package sort;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/11/6 16:58
 */
public class HeapSort {
    public static void swap(long[] array, int i, int j) {
        long t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
    /**
     * 堆排序：
     *
     * 时间复杂度：
     * 最好/平均/最坏：O(n * log(n))
     *
     * 空间复杂度：O(1)
     *
     * 稳定性：不稳定（向下调整的过程中，相对位置可能被破坏）
     * @param array
     */
    public static void adjustDown大堆(long[] array, int size, int index) {
        while (2 * index + 1 < size) {
            int maxIdx = 2 * index + 1;
            if (maxIdx + 1 < size && array[maxIdx + 1] > array[maxIdx]) {
                maxIdx++;
            }

            if (array[index] >= array[maxIdx]) {
                return;
            }

            swap(array, index, maxIdx);

            index = maxIdx;
        }
    }

    public static void createHeap大堆(long[] array, int size) {
        for (int i = (size - 2) / 2; i >= 0; i--) {
            adjustDown大堆(array, size, i);
        }
    }

    public static void heapSort(long[] array) {
        // 将整个数组（整个数组都是无序区间）创建成大堆
        createHeap大堆(array, array.length);

        // 循环选择的过程，一共需要 n - 1 次
        for (int i = 0; i < array.length - 1; i++) {
            // 无序区间: [0, array.length - i)
            // 交换最大的元素（下标是 [0]）和无序区间的最后一个元素（下标是 array.length - i - 1）
            swap(array, 0, array.length - i - 1);
            // 由于最大的元素已经放到最后了，所以，无序区间：[0, array.length - i - 1)
            // 无序区间的元素个数: array.length - i - 1 - 0 = array.length - i - 1
            // 为了维护无序区间的大堆性质，对无序区间剩余的元素，在 [0] 做向下调整
            adjustDown大堆(array, array.length - i - 1, 0);
        }
    }
}
